package main
import "sort"
import . "nc_tools"
/*
 * type Interval struct {
 *   Start int
 *   End int
 * }
 */
func merge(intervals []*Interval) []*Interval {
    n := len(intervals)
    if n == 0 {
        return nil
    }
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i].Start < intervals[j].Start
    })
    res := []*Interval{intervals[0]}
    max := func(a, b int) int {
        if a > b {
            return a
        }
        return b
    }
    for i := 1; i < n; i++ {
        if intervals[i].Start <= res[len(res)-1].End {
            res[len(res)-1].End = max(res[len(res)-1].End, intervals[i].End)
        } else {
            res = append(res, intervals[i])
        }
    } 
    return res
}